#include <vector>

using namespace std;

// 二维接雨水
// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
// 请计算图中形状最多能接多少体积的雨水。
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/

class Solution 
{
public:
    int trapRainWater(vector<vector<int>>& heightMap) 
    {
        int m = heightMap.size(), n = heightMap[0].size();
        if(m <= 2 || n <= 2) return 0; // 无法接到水
        
        // first : 水线  second : 压缩后的坐标 pos
        // 将水线放在 first 位置上的目的是，能够借助标准库中实现的比较函数，不用自己实现
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        bool visited[m][n];
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i == 0 || i == m - 1 || j == 0 || j == n - 1)
                {
                    q.emplace(heightMap[i][j], i * n + j);
                    visited[i][j] = true;
                }
            }
        }

        int ret = 0;
        int move[] = {-1, 0, 1, 0, -1};
        while(!q.empty())
        {
            auto [w, p] = q.top();
            q.pop();
            // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
            // 记 pos = x * n + y，则 x = pos / n，y = pos % n  
            int x = p / n, y = p % n;
            ret += w - heightMap[x][y]; // w >= heightMap[x][y]
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + move[k], ny = y + move[k + 1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny])
                {
                    q.emplace(max(heightMap[nx][ny], w), nx * n + ny);
                    visited[nx][ny] = true;
                }
            }
        }
        return ret;
    }
};